/**
 * \file map.c
 * \brief Inside the table, special key values are of type R_VALUE_SPEC:
 * - if key.val_int == EMPTY_BUCKET: this is an empty bucket.
 * - if key.val_int == LAZY_BUCKET: this is an empty bucket that was lazily
 * deleted. We lazily delete buckets so that we wouldn't have to rehash every
 * time a deletion occurs (because that could interfere with the quadratic
 * probing strategy).
 **/

#include "map.h"
#include "mem.h"

/* Special key values, see above: */
#define EMPTY_BUCKET 0
#define LAZY_BUCKET 1

/* Macros to deal with these key values: val is of type RValue (should be
 * a key) */
#define r_map_is_empty(val) (((val).type == R_VALUE_SPEC) \
                               and ((val).val_int == EMPTY_BUCKET))

#define r_map_is_lazy(val)  (((val).type == R_VALUE_SPEC) \
                               and ((val).val_int == LAZY_BUCKET))

#define r_map_is_spec(val)  ((val).type == R_VALUE_SPEC)

/**
 * \brief Get the n-th bucket.
 **/
static inline RMapPair r_map_bucket_get(RMap* map, uint32_t n);

/**
 * \brief Set the n-th bucket.
 **/
static inline void r_map_bucket_set(RMap* map, uint32_t n, RValue key,
                                     RValue value);

/**
 * \brief Clear a list of buckets of size n.
 **/
static inline void r_map_buckets_clear(RMapPair* buckets, int n);

/**
 * \brief Create a Map of exactly size n.
 **/
static RValue r_map_new_exact(int n);

/**
 * \brief Get a prime number larger than n, smaller than the next power of 2.
 **/
static uint32_t r_map_prime(uint32_t n);

/**
 * \brief Put a key into the bucket list.
 * \return true if key is already present there (overwritten).
 **/
static bool r_map_set2(RMapPair* buckets, uint32_t n,
                        RValue key, RValue value);

RMapPair r_map_bucket_get(RMap* map, uint32_t n)
{
  assert(n < map->size);
  return map->buckets[n];
}

void r_map_bucket_set(RMap* map, uint32_t n, RValue key,
                       RValue value)
{
  assert(n < map->size);
  map->buckets[n].key = key;
  map->buckets[n].value = value;
}

void r_map_buckets_clear(RMapPair* buckets, int n)
{
  int i;
  RValue clear;
  clear.type = R_VALUE_SPEC;
  clear.val_int = EMPTY_BUCKET;
  for (i = 0; i < n; i++){
    buckets[i].key = clear;
  }
}

bool r_map_get(RValue mapv, RValue key, RValue* value)
{
  assert(mapv.type == R_VALUE_MAP);
  RMap* map = mapv.val_map;

  uint32_t i;
  uint32_t hash = r_value_hash(key) % map->size;
  for (i = 0; i < map->size; i++){
    /* Quadratic probing: */
    uint32_t loc = (hash + i*i) % map->size;

    if (r_map_is_empty(map->buckets[loc].key)){
      /* Hit an empty bucket, end of quadratic probing */
      return false;
    } else if (r_value_equal(key, map->buckets[loc].key)){
      /* Found the key */
      *value = map->buckets[loc].value;
      return true;
    }
  }

  /* Lazy elements form a cycle, this key doesn't exist here: */
  return false;
}

RValue r_map_new()
{
  #define MAP_DEFAULT_SIZE 13
  return r_map_new_exact(MAP_DEFAULT_SIZE);
}

RValue r_map_new_exact(int n)
{
  RValue map;
  map.type = R_VALUE_MAP;
  map.val_map = (RMap*) r_mem_malloc(sizeof(RMap));
  map.val_map->size = n;
  map.val_map->filled = 0;
  map.val_map->buckets = (RMapPair*) r_mem_malloc(n*sizeof(RMapPair));
  r_map_buckets_clear(map.val_map->buckets, n);
  return map;
}

RValue r_map_new_sized(int n)
{
  return r_map_new_exact(r_map_prime(n));
}

uint32_t r_map_prime(uint32_t n)
{
  /* Size of the sizes[] list */
  #define MAP_PRIMES 27

  /* This list was generated by a script that is in closet. */
  const uint32_t sizes[] = {13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191,
                            16381, 32749, 65521, 131071, 262139, 524287,
                            1048573, 2097143, 4194301, 8388593, 16777213,
                            33554393, 67108859, 134217689, 268435399,
                            536870909, 1073741789};

  int i;
  for (i = 0; i < MAP_PRIMES - 1; i++) {
    if (n < sizes[i])
      return sizes[i];
  }

  /* Otherwise, return the largest possible hash table size. */
  return sizes[MAP_PRIMES - 1];
}

bool r_map_set(RValue mapv, RValue key, RValue value)
{
  assert(r_value_is_map(mapv));

  RMap* map = mapv.val_map;
  if (map->filled + 1 > map->size / 2) {
    /* The hash table is overfilled. */
    uint32_t new_size = r_map_prime(map->size + 1);

    /* Allocate necessary space */
    RMapPair* new_buckets = (RMapPair*) r_mem_malloc(
                                             sizeof(RMapPair) * new_size);

    /* Hash into the new buckets */
    int i;
    for (i = 0; i < map->size; i++){
      if (not r_map_is_spec(map->buckets[i].key))
        r_map_set2(new_buckets, new_size, map->buckets[i].key,
                    map->buckets[i].value);
    }
    map->size = new_size;
    map->buckets = new_buckets;
  }
  map->filled++;
  return r_map_set2(map->buckets, map->size, key, value);
}

bool r_map_set2(RMapPair* buckets, uint32_t n, RValue key,
                 RValue value)
{
  uint32_t hash = r_value_hash(key) % n;
  int i;

  for (i = 0; i < n; i++){
    /* Quadratic probing */
    int loc = (hash + i*i) % n;

    if (r_map_is_spec(buckets[loc].key)){
      /* found an empty spot */
      buckets[loc].key = key;
      buckets[loc].value = value;
      return false;
    } else if (r_value_equal(key, buckets[loc].key)){
      /* found the same key */
      buckets[loc].key = key;
      buckets[loc].value = value;
      return true;
    }
    /* otherwise keep going */
  }

  /* TODO: Should never reach this point, report an error. */
  assert_never();
  return false;
}
